//#include<iostream>
//#include<vector>
//#include<stack>
//#include<string>
//using namespace std;
////vector<vector<int>> v;
////vector<bool> flag(7,false);
////vector<int> path;
////void dfs(vector<int>& nums)
////{
////    if (path.size() == nums.size())
////    {
////        v.push_back(path);
////        return;
////    }
////    for (int i = 0; i < nums.size(); i++)
////    {
////        if (flag[i] == false)
////        {
////            path.push_back(nums[i]);
////            flag[i] = true;
////            dfs(nums);
////            flag[i] = false;
////            path.pop_back();
////        }
////    }
////}
////vector<vector<int>> permute(vector<int>& nums) {
////    dfs(nums);
////    return v;
////}
////
////
////int main()
////{
////    vector<int> v{ 1,2,3 };
////    permute(v);
////    return 0;
////}
////vector<string> v{ "",    " ",   "abc",  "def", "ghi","jkl", "mno", "pqrs", "tuv", "wxyz" };
////vector<string> ret;
////string path;
////int sign = 0;
////void dfs(string digits, int i);
////vector<string> letterCombinations(string digits) {
////    dfs(digits, digits[0] - '0');
////    return ret;
////}
////void dfs(string digits, int i)
////{
////    if (path.size() == digits.size())
////    {
////        ret.push_back(path);
////        return;
////    }
////    for (int x = 0; x < v[i].size(); x++)
////    {
////        path += v[i][x];
////        dfs(digits, digits[i + 1] - '0');
////        path.pop_back();
////    }
////}
////int main()
////{
////    letterCombinations("234");
////    return 0;
////}
////vector<string> ret;
////bool flag[17];
////string path;
////bool Isavalid(stack<char>& s, string& path);
////void dfs(vector<char>& nums);
////vector<string> generateParenthesis(int n) {
////    vector<char> nums;
////    for (int i = 0; i < n; i++)
////    {
////        nums.push_back('(');
////    }
////    for (int i = 0; i < n; i++)
////    {
////        nums.push_back(')');
////    }
////    dfs(nums);
////    return ret;
////}
////void dfs(vector<char>& nums)
////{
////    if (path.size() == nums.size())
////    {
////        stack<char> s;
////        if (Isavalid(s, path))
////            ret.push_back(path);
////        return;
////    }
////    for (int i = 0; i < nums.size(); i++)
////    {
////        if (flag[i] == true || (i != 0 && nums[i] == nums[i - 1] && nums[i - 1] == false)) continue;
////        path += nums[i];
////        flag[i] = true;
////        dfs(nums);
////        path.pop_back();
////        flag[i] = false;
////    }
////}
////bool Isavalid(stack<char>& s, string& path)
////{
////    for (auto ch : path)
////    {
////        if (ch == '(') s.push(ch);
////        if (ch == ')')
////        {
////            if (!s.empty()) s.pop();
////            else return false;
////        }
////    }
////    return s.empty();
////}
////vector<vector<int>> ret;
////vector<int> path;
////int flag = 0;
////void dfs(vector<int>& candidates, int target, int count);
////vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
////    int count = 0;
////    dfs(candidates, target, count);
////    return ret;
////}
////void dfs(vector<int>& candidates, int target, int count)
////{
////    if (count > flag) return;
////    if (count == target)
////    {
////        ret.push_back(path);
////        flag = 1;
////        return;
////    }
////    if (flag == 1)
////    {
////        flag = 0;
////        return;
////    }
////    for (int i = 0; i < candidates.size(); i++)
////    {
////        path.push_back(candidates[i]);
////        count += candidates[i];
////        dfs(candidates, target, count);
////        path.pop_back();
////        count -= candidates[i];
////    }
////}
////int main()
////{
////    vector<int> v{ 2,3,6,7 };
////    combinationSum(v, 7);
////    return 0;
////}
//string path;
//vector<string> ret;
//void dfs(string s, int x)
//{
//    if (path.size() == s.size())
//    {
//        ret.push_back(path);
//        return;
//    }
//    for (int i = x; i < s.size(); i++)
//    {
//        if (s[i] <= 'z' && s[i] >= 'a')
//        {
//            path += s[i] + 'A' - 'a';
//            dfs(s, i + 1);
//            path.pop_back();
//            path += s[i];
//            dfs(s, i + 1);
//            path.pop_back();
//        }
//        else if (s[i] <= 'z' && s[i] >= 'A')
//        {
//            path += s[i] - 'A' + 'a';
//            dfs(s, i + 1);
//            path.pop_back();
//            path += s[i];
//            dfs(s, i + 1);
//            path.pop_back();
//        }
//        else continue;
//    }
//}
//vector<string> letterCasePermutation(string s) {
//    dfs(s, 0);
//    return ret;
//}
//
//int main()
//{
//    letterCasePermutation("a1b2");
//    return 0;
//}
class Solution {
public:
    double myPow(double x, long long n) {
        if (n == 0)
            return 1.0;
        if (n < 0) {
            x = 1 / x;
            n = -n;
        }
        double tmp = myPow(x, n / 2);
        return n % 2 == 1 ? tmp * tmp * x : tmp * tmp;
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool evaluateTree(TreeNode* root) {
        if (root->right == nullptr) return root->val;
        bool right = evaluateTree(root->right);
        bool left = evaluateTree(root->left);
        return root->val == 2 ? right || left : right && left;
    }
};